package com.java.comprehensive.arithmetic.leecode.easy;

import java.util.Stack;

/**
 * 150. 逆波兰表达式求值
 * 中等
 * 626
 * 相关企业
 * 根据 逆波兰表示法，求表达式的值。
 *
 * 有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
 *
 * 注意 两个整数之间的除法只保留整数部分。
 *
 * 可以保证给定的逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
 *
 * 注：给定大的数组合法并且是二叉树后续遍历（他其实是后缀）组成中缀串计算
 */
public class LeetCode_105 {
    public static int evalRPN(String[] tokens) {
        //
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < tokens.length; i++) {
            if (tokens[i].equals("+") || tokens[i].equals("/") || tokens[i].equals("*") || tokens[i].equals("-")) {
                Integer pop = stack.pop();
                Integer pop1 = stack.pop();
                if (tokens[i].equals("+")) {
                    stack.push(pop + pop1);
                } else if (tokens[i].equals("-")) {
                    stack.push(-pop + pop1);
                } else if (tokens[i].equals("*")) {
                    stack.push(pop1 * pop);
                } else if (tokens[i].equals("/")) {
                    stack.push(pop1 / pop);
                }
            } else {
                stack.push(Integer.parseInt(tokens[i]));
            }
        }
        return stack.pop();
    }

    public static void main(String[] args) {
        String[] tokens = {"4", "13", "5", "/", "+"};
        int i = evalRPN(tokens);
        System.out.println(i);
    }
}
